// ++++++++++++++++++++++++++++++++++++++++
// 《零基础Go语言算法实战》源码
// ++++++++++++++++++++++++++++++++++++++++
// Author:廖显东（ShirDon）
// Blog:https://www.shirdon.com/
// Gitee:https://gitee.com/shirdonl/goAlgorithms.git
// Buy link :https://item.jd.com/14101229.html
// ++++++++++++++++++++++++++++++++++++++++

package main

import (
	"fmt"
)

type ListNode struct {
	Data int
	Next *ListNode
}

func sortList(head *ListNode) *ListNode {
	length := 0
	cur := head
	for cur != nil {
		length++
		cur = cur.Next
	}
	if length <= 1 {
		return head
	}

	middleNode := middleNode(head)
	cur = middleNode.Next
	middleNode.Next = nil
	middleNode = cur

	left := sortList(head)
	right := sortList(middleNode)
	return mergeTwoLists(left, right)
}

func middleNode(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	list1 := head
	list2 := head
	for list2.Next != nil && list2.Next.Next != nil {
		list1 = list1.Next
		list2 = list2.Next.Next
	}
	return list1
}

func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
	if list1 == nil {
		return list2
	}
	if list2 == nil {
		return list1
	}
	if list1.Data < list2.Data {
		list1.Next = mergeTwoLists(list1.Next, list2)
		return list1
	}
	list2.Next = mergeTwoLists(list1, list2.Next)
	return list2
}

func main() {
	listNode := &ListNode{8, &ListNode{18, &ListNode{6, &ListNode{3, nil}}}}
	res := sortList(listNode)
	fmt.Println(res.Data)
	fmt.Println(res.Next.Data)
	fmt.Println(res.Next.Next.Data)
	fmt.Println(res.Next.Next.Next.Data)
}

//$ go run interview6-8.go
//3
//6
//8
//18
